package com.zzy;


import java.io.*;
import java.util.*;

/**
 * @author zhuZhaoYang
 * @date 2021/9/27 10:31
 */
public class EightPuzzle {
    public static final int[] DX = new int[]{0, 1, 0, -1};
    public static final int[] DY = new int[]{-1, 0, 1, 0};
    public static final int MIN_X = 0;
    public static final int MIN_Y = 0;
    public static final int MAX_X = 2;
    public static final int MAX_Y = 2;

    public static void main(String[] args) {
        LinkedList<LinkedList<Integer>> start;
        LinkedList<LinkedList<Integer>> goal;
        EightPuzzle eightPuzzle = new EightPuzzle();
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入初始棋盘数据文件路径：");
        String startPath = scanner.nextLine();
        start = eightPuzzle.readFromFile(startPath);
        if (start == null) {
            System.out.println("初始棋盘读取失败！");
            return;
        }
        System.out.println("请输入目标棋盘数据文件路径：");
        String goalPath = scanner.nextLine();
        scanner.close();
        goal = eightPuzzle.readFromFile(goalPath);
        if (goal == null) {
            System.out.println("目标棋盘读取失败！");
            return;
        }

        System.out.println("====初始棋盘====");
        for (LinkedList<Integer> integers : start) {
            for (Integer integer : integers) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }

        System.out.println("====目标棋盘====");
        for (LinkedList<Integer> integers : goal) {
            for (Integer integer : integers) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }

        //判断是否有解，即初始和目标状态的逆序数奇偶性是否相同
        int startInversion = eightPuzzle.getInversion(start);
        System.out.println("初始棋盘逆序对为：" + startInversion);
        int goalInversion = eightPuzzle.getInversion(goal);
        System.out.println("目标棋盘逆序对为：" + goalInversion);
        if (!(startInversion % 2 == goalInversion % 2)) {
            System.out.println("此棋盘无解");
            return;
        } else {
            System.out.println("此棋盘有解");
        }
        System.out.println("====盲目式搜索结果====");
        eightPuzzle.bfs(start, goal);
        System.out.println("====  A* 搜索结果====");
        eightPuzzle.aStart(start, goal);


    }

    /**
     * 从文件读取棋盘
     *
     * @param path 文件路径
     * @return 存放在二维数组中的棋盘
     */
    public LinkedList<LinkedList<Integer>> readFromFile(String path) {
        LinkedList<LinkedList<Integer>> bord = new LinkedList<>();
        File file = new File(path);
        if (!file.exists()) {
            System.out.println("文件" + path + "不存在");
            return null;
        }
        BufferedReader bufferedReader;
        try {
            bufferedReader = new BufferedReader(new FileReader(file));
            String line;
            while ((line = bufferedReader.readLine()) != null) {
                String[] nums = line.split(" ");
                LinkedList<Integer> raw = new LinkedList<>();
                for (String num : nums) {
                    raw.add(Integer.valueOf(num));
                }
                bord.add(raw);
            }
        } catch (IOException e) {
            e.printStackTrace();
            return null;
        }
        return bord;
    }

    /**
     * 盲目式广度优先搜索，子节点为除前置节点的移动方向状态
     *
     * @param goal  目标棋盘
     * @param start 初始棋盘
     */
    public void bfs(LinkedList<LinkedList<Integer>> start, LinkedList<LinkedList<Integer>> goal) {
        Queue<Node> nodeQueue = new LinkedList<>();
        int searchTimes = 0;
        //初始节点，加入队列
        int[] startIndex = getStartIndex(start);
        Node node = new Node(startIndex[0], startIndex[1], new Node(-1, -1, null, null), start);
        nodeQueue.add(node);
        while (!nodeQueue.isEmpty()) {
            Node topNode = nodeQueue.poll();
            if (atGoal(topNode, goal)) {
                //输出结果
                printAns(topNode, searchTimes);
                return;
            }
            for (int i = 0; i < DX.length; i++) {
                int nextX = topNode.x + DX[i];
                int nextY = topNode.y + DY[i];
                //前置节点跳过
                if (nextX == topNode.preNode.x && nextY == topNode.preNode.y) {
                    continue;
                }
                //越界则跳过
                if (!(nextX >= MIN_X && nextX <= MAX_X && nextY >= MIN_Y && nextY <= MAX_Y)) {
                    continue;
                }
                LinkedList<LinkedList<Integer>> bord = new LinkedList<>();
                myClone(topNode.bord, bord);
                //交换,相当于改变棋盘
                int temp = bord.get(nextX).get(nextY);
                bord.get(nextX).set(nextY, bord.get(topNode.x).get(topNode.y));
                bord.get(topNode.x).set(topNode.y, temp);
                //将子状态加入队列
                nodeQueue.add(new Node(nextX, nextY, topNode, bord));
            }
            searchTimes++;
        }
    }

    /**
     * A*搜索
     *
     * @param goal  目标棋盘
     * @param start 起始棋盘
     */
    public void aStart(LinkedList<LinkedList<Integer>> start, LinkedList<LinkedList<Integer>> goal) {
        Queue<Node> nodeQueue = new PriorityQueue<>();
        int searchTimes = 0;
        //初始节点，加入队列
        int[] startIndex = getStartIndex(start);
        Node node = new Node(startIndex[0], startIndex[1],
                new Node(-1, -1, null, null, Integer.MAX_VALUE, -1),
                start, getEvaluate(start, goal), 0);
        nodeQueue.add(node);
        while (!nodeQueue.isEmpty()) {
            Node topNode = nodeQueue.poll();
            if (atGoal(topNode, goal)) {
                //输出结果
                printAns(topNode, searchTimes);
                return;
            }
            for (int i = 0; i < DX.length; i++) {
                int nextX = topNode.x + DX[i];
                int nextY = topNode.y + DY[i];
                //前置节点跳过
                if (nextX == topNode.preNode.x && nextY == topNode.preNode.y) {
                    continue;
                }
                //越界则跳过
                if (!(nextX >= MIN_X && nextX <= MAX_X && nextY >= MIN_Y && nextY <= MAX_Y)) {
                    continue;
                }
                LinkedList<LinkedList<Integer>> bord = new LinkedList<>();
                myClone(topNode.bord, bord);
                //交换,相当于改变棋盘
                int temp = bord.get(nextX).get(nextY);
                bord.get(nextX).set(nextY, bord.get(topNode.x).get(topNode.y));
                bord.get(topNode.x).set(topNode.y, temp);
                //将子状态加入队列
                nodeQueue.add(new Node(nextX, nextY, topNode, bord, getEvaluate(bord, goal), topNode.deep + 1));
            }
            searchTimes++;
        }
    }

    /**
     * 估值函数
     *
     * @param bord 当前棋盘
     * @return 当前棋盘到目标棋盘的预估路径值
     */
    public int getEvaluate(LinkedList<LinkedList<Integer>> bord, LinkedList<LinkedList<Integer>> goal) {
        int ans = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int dis = bord.get(i).get(j) - goal.get(i).get(j);
                ans += dis > 0 ? dis : -dis;
            }
        }
        return ans;
    }

    /**
     * 获取逆序对数
     *
     * @param bord 棋盘
     * @return 逆序对数
     */
    public int getInversion(LinkedList<LinkedList<Integer>> bord) {
        int ans = 0;
        LinkedList<Integer> arr = new LinkedList<>();
        for (LinkedList<Integer> integers : bord) {
            for (Integer integer : integers) {
                if (integer != 0) {
                    arr.add(integer);
                }
            }
        }
        for (int i = 0; i < arr.size(); i++) {
            for (int j = i; j < arr.size(); j++) {
                if (arr.get(i) > arr.get(j)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    public int[] getStartIndex(LinkedList<LinkedList<Integer>> bord) {
        for (int i = 0; i < bord.size(); i++) {
            for (int j = 0; j < bord.get(i).size(); j++) {
                if (bord.get(i).get(j) == 0) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }

    /**
     * 浅拷贝
     *
     * @param old  旧棋盘
     * @param bord 待填充棋盘
     */
    public void myClone(LinkedList<LinkedList<Integer>> old, LinkedList<LinkedList<Integer>> bord) {
        for (LinkedList<Integer> integers : old) {
            LinkedList<Integer> raw = new LinkedList<>(integers);
            bord.add(raw);
        }
    }

    /**
     * 验证是否为目标节点
     *
     * @param node 当前节点
     * @return 是否为目标节点
     */
    public boolean atGoal(Node node, LinkedList<LinkedList<Integer>> goal) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (!node.bord.get(i).get(j).equals(goal.get(i).get(j))) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 打印搜索结果
     *
     * @param pNode 目标状态节点
     */
    public void printAns(Node pNode, int searchTimes) {
        System.out.println("搜索次数：" + searchTimes);
        StringBuilder stringBuilder = new StringBuilder();
        int len = 0;
        while (pNode.preNode != null) {
            len++;
            int difX = pNode.preNode.x - pNode.x;
            int difY = pNode.preNode.y - pNode.y;
            if (difX == 0 && difY == 1) {
                stringBuilder.insert(0, "← ");
            }
            if (difX == 0 && difY == -1) {
                stringBuilder.insert(0, "→ ");
            }
            if (difX == 1 && difY == 0) {
                stringBuilder.insert(0, "↑ ");
            }
            if (difX == -1 && difY == 0) {
                stringBuilder.insert(0, "↓ ");
            }
            pNode = pNode.preNode;
        }
        System.out.println("结果路径：" + stringBuilder.toString());
        System.out.println("路径长度为：" + (len - 1));
    }

    /**
     * 状态节点类 实现Comparable接口并重写compareTo方法
     * 用于优先队列排序
     * <p>
     * deep 当前节点深度
     * dis 到目标节点的预估值
     */
    private static class Node implements Comparable<Node> {

        public Node(int x, int y, Node preNode, LinkedList<LinkedList<Integer>> bord, int dis, int deep) {
            this.x = x;
            this.y = y;
            this.bord = bord;
            this.dis = dis;
            this.deep = deep;
            this.preNode = preNode;
        }

        public Node(int x, int y, Node preNode, LinkedList<LinkedList<Integer>> bord) {
            this.x = x;
            this.y = y;
            this.bord = bord;
            this.preNode = preNode;
        }

        int x;
        int y;
        int dis;
        int deep;
        LinkedList<LinkedList<Integer>> bord;
        Node preNode;

        @Override
        public int compareTo(Node node) {
            return (this.dis + this.deep) - (node.dis + node.deep);
        }
    }
}
